package com.my.study.algorithm.leetcode;

import java.util.Arrays;

/**
 * 编辑距离
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 *
 * 你可以对一个单词进行如下三种操作：
 *
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 
 * @author Carlos
 * @version 1.0.0
 * @date 2023/3/12 10:12
 */
public class EditDistance {
    
    private char[] s, t;
    private int[][] cache;
    
    public int minDistance(String text1, String text2) {
        s = text1.toCharArray();
        t = text2.toCharArray();
        int n = s.length;
        int m = t.length;
        
        cache = new int[n][m];

        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        return dfs(n-1, m-1);
    }
    
    private int dfs(int i, int j) {
        if (i < 0) {
            return j + 1;
        }
        if (j < 0) {
            return i + 1;
        }
        if (cache[i][j] != -1) {
            return cache[i][j];
        }
        if (s[i] == t[j]) {
            return dfs(i-1, j- 1);
        }
        return cache[i][j] = Math.min(Math.min(dfs(i,j-1), dfs(i-1, j)), dfs(i-1, j-1)) + 1;
    }
    
}
